事实上,这篇题解跟线段树没有任何关系。
lifan 让我们用 CDQ 做,但他的标程是假的。
先考虑单点修改+区间求和
数组的初值可以看做 个修改操作。
将询问操作拆成 和 两个区间的差。
那么修改 对询问 有贡献的条件为:
很显然,这是一个二维偏序,具体实现很简单就不讲了。
回到区间修改,一样将修改操作拆成两个区间。
在两个相邻修改区间右端点之间的数修改的值是一样的,所以可以维护这个值。
区间加就可以变为 任意两个相邻修改区间右端点的距离与该部分修改的值的乘积 的和。
不会写归并排序,就用了 STL 里的 merge。
时间复杂度均为 ,跑不过树状数组/线段树。
所以写这个的意义何在
单点修改+区间查询:
#include <cstdio>
#include <algorithm>
using namespace std;
const int MAXN = 4e6;
int n , m , t , q , Ans[ MAXN + 5 ];
struct node {
int x , ty , val , id;
}a[ MAXN + 5 ] , tmp[ MAXN + 5 ];
bool cmp2( const node &x , const node &y ) {
return x.x < y.x;
}
void CDQ( int l , int r ) {
if( l == r ) return;
int Mid = ( l + r ) >> 1;
CDQ( l , Mid ); CDQ( Mid + 1 , r );
merge( a + l , a + Mid + 1 , a + Mid + 1 , a + r + 1 , tmp + l , cmp2 );
//sort( a + l , a + Mid + 1 , cmp2 ); sort( a + Mid + 1 , a + r + 1 , cmp2 );
int Sum = 0;
int i = l , j = Mid + 1; //i->[l,Mid] j->(Mid,r]
for( ; j <= r ; j ++ ) {
for( ; i <= Mid && a[ i ].x <= a[ j ].x ; i ++ ) if( a[ i ].ty == 1 ) Sum += a[ i ].val;
if( a[ j ].ty == 2 ) Ans[ a[ j ].id ] += a[ j ].val * Sum;
}
for( int i = l ; i <= r ; i ++ ) a[ i ] = tmp[ i ];
}
int main( ) {
scanf("%d %d",&n,&m);
for( int i = 1 , x ; i <= n ; i ++ ) {
scanf("%d",&x);
a[ ++ t ] = { i , 1 , x };
}
for( int i = 1 , opt , l , r , x ; i <= m ; i ++ ) {
scanf("%d %d %d",&opt,&l,&r);
if( opt == 1 ) {
a[ ++ t ] = { l , 1 , r };
}
if( opt == 2 ) {
++ q;
a[ ++ t ] = { l - 1 , 2 , -1 , q };
a[ ++ t ] = { r , 2 , 1 , q };
}
}
m = t;
CDQ( 1 , m );
for( int i = 1 ; i <= q ; i ++ ) printf("%d\n", Ans[ i ] );
return 0;
}
区间修改+区间查询
#include <cstdio>
#include <algorithm>
using namespace std;
#define LL long long
const int MAXN = 5e6;
int n , m , t , q;
LL Ans[ MAXN + 5 ];
struct node {
int x , ty , val , id;
}a[ MAXN + 5 ] , tmp[ MAXN + 5 ];
bool cmp2( const node &x , const node &y ) {
return x.x < y.x;
}
void CDQ( int l , int r ) {
if( l == r ) return;
int Mid = ( l + r ) >> 1;
CDQ( l , Mid ); CDQ( Mid + 1 , r );
merge( a + l , a + Mid + 1 , a + Mid + 1 , a + r + 1 , tmp + l , cmp2 );
LL Sum = 0 , val = 0; int last = 0;
int i = l , j = Mid + 1; //i->[l,Mid] j->(Mid,r]
for( ; j <= r ; j ++ ) {
for( ; i <= Mid && a[ i ].x <= a[ j ].x ; i ++ ) {
Sum += ( a[ i ].x - last ) * val; last = a[ i ].x;
if( a[ i ].ty == 1 ) val += a[ i ].val;
}
Sum += ( a[ j ].x - last ) * val; last = a[ j ].x;
if( a[ j ].ty == 2 ) Ans[ a[ j ].id ] += a[ j ].val * Sum;
}
for( int i = l ; i <= r ; i ++ ) a[ i ] = tmp[ i ];
}
int main( ) {
scanf("%d %d",&n,&m);
for( int i = 1 , x ; i <= n ; i ++ ) {
scanf("%d",&x);
a[ ++ t ] = { i - 1 , 1 , x };
a[ ++ t ] = { i , 1 , -x };
}
for( int i = 1 , opt , l , r , x ; i <= m ; i ++ ) {
scanf("%d %d %d",&opt,&l,&r);
if( opt == 1 ) {
scanf("%d",&x);
a[ ++ t ] = { l - 1 , 1 , x };
a[ ++ t ] = { r , 1 , -x };
}
if( opt == 2 ) {
++ q;
a[ ++ t ] = { l - 1 , 2 , -1 , q };
a[ ++ t ] = { r , 2 , 1 , q };
}
}
m = t;
CDQ( 1 , m );
for( int i = 1 ; i <= q ; i ++ ) printf("%lld\n", Ans[ i ] );
return 0;
}